package leetcode_2301_2400;

import java.util.*;

public class LeeCode_2368 {
    public static void main(String[] args) {
        System.out.println(reachableNodes(7, new int[][]{{0, 1}, {1, 2}, {3, 1}, {4, 0}, {0, 5}, {5, 6}},
                new int[]{4, 5}));
    }
    private static int reachableNodes(int n, int[][] edges, int[] restricted) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        Set<Integer> fob = new HashSet<>();
        for (int i : restricted) {
            fob.add(i);
        }
        for (int[] e : edges) {
            if (fob.contains(e[0]) || fob.contains(e[1])){
                continue;
            }
            if (map.containsKey(e[0])){
                map.get(e[0]).add(e[1]);
            }else {
                List<Integer> list = new ArrayList<>();
                list.add(e[1]);
                map.put(e[0], list);
            }
            if (map.containsKey(e[1])){
                map.get(e[1]).add(e[0]);
            }else {
                List<Integer> list = new ArrayList<>();
                list.add(e[0]);
                map.put(e[1], list);
            }
        }
        return dfs(map, new HashSet<>(), 0, 1);
    }
    private static int dfs(Map<Integer, List<Integer>> map, Set<Integer> used, int now, int count){
        int plus = 1;
        used.add(now);
        if (!map.containsKey(now)){
            return plus;
        }
        for (Integer next : map.get(now)) {
            if (used.contains(next)){
                continue;
            }
            plus += dfs(map, used, next, 1);
        }
        return plus;
    }
}
